class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        def expand(i, j):
            while i >= 0 and j < n and s[i] == s[j]:
                i -= 1
                j += 1
            return (j - i - 2) // 2

        s = '#' + '#'.join(s) + '#'
        n = len(s)
        p = [0] * n
        p[1] = 1
        right_max = 2
        center = 1
        for i in range(2, n):
            if i >= right_max:
                p[i] = expand(i, i)
                right_max = i + p[i]
                center = i
            else:
                morrior_i = 2 * center - i
                r = min(right_max - i, p[morrior_i])
                R = expand(i - r, i + r)
                p[i] = R
                if R > r:
                    right_max = i + R
                    center = i
        r = max(p)
        index = p.index(r)
        return s[index - r + 1: index + r: 2]



data = Solution()
s = "babcd"
print(data.longestPalindrome(s))